Abstract
The beautiful, branching structure of ice is one of the most striking visual phenomena of the winter landscape. Yet there is little study about modeling this effect in computer graphics. In this paper, we present a novel approach for visual simulation of ice growth. We use a numerical simulation technique from computational physics, the “phase field method,” and modify it to allow aesthetic manipulation of ice crystal growth. We present acceleration techniques to achieve interactive simulation performance, as well as a novel geometric sharpening algorithm that removes some of the smoothing artifacts from the implicit representation. We have successfully applied this approach to generate ice crystal growth on 3D object surfaces in several scenes.
Introduction
The geometrically and optically complex structure of ice is one of the most striking visual phenomena in winter. These beautiful, branching patterns of ice can be found on many exposed surfaces, such as sidewalks, panes of glass, and hoods of cars. Together, these surfaces comprise a unique aspect of the frozen, wintery landscape.
While there exists some work that models this visual complexity [26, 28], there has been relatively little research in computer graphics that attempts to physically simulate the growth of ice patterns. In addition, none of the previous work presents a mechanism that allows an artist to automatically adjust the simulation parameters to achieve a specific visual effect. However, there is a large body of knowledge in both crystal growth and computational physics that addresses the computation of the liquid to solid phase transition. There exists a wide morphology of ice patterns, and in this paper we present a model that can simulate several different types of solidification, most notably dendritic solidification, which is the most geometrically complex and visually interesting of all ice structures.
Previous Work
In this section, we briefly survey related simulation and ren¬dering techniques from the computer graphics and computational physics literature.
Visual Simulation Methods for Water in Different States
The visual simulation and modeling of the other states of H2O have been well-studied in the past. The dynamics of water and steam have been impressively captured in general fluid simulations [7, 9]. Recently, Fearing8 examined the solid state of water when simulating the dynamics of fallen snow. However, the analysis in his paper focused on the phenom¬ena that arise in deposition and drift of snow, not those that arise in the liquid to solid phase transition. Instead, it as¬sumed that all phase transitions had already taken place in the sky. Consequently, the lack of ice in Fearing’s scenes is noticeable.
A famous empirical algorithm that attempts to capture the structure of dendritic ice is the Koch snowflake. First described by Helge von Koch in 1904 26, it defines simple production rules that, when applied recursively, produces a structure that is in close visual agreement with that of a snowflake. The reader is referred to The Fractal Geometry of Nature17 for further details. While it renders visually plausi¬ble results, the Koch snowflake has no clear physical basis and certainly does not allow for an aesthetic parameterization.
Diffusion Limited Aggregation, or DLA,2, 28 is a tech¬nique from physics that attempts to capture similar effects to the ones we describe here. Notably, this technique deals with solidification in the context of vapor deposition, the aggregation of water molecules in the air onto a cold surface. Instead, we present a method that models the aggregation of liquid molecules on a crystal in an undercooled melt.
Simulation Techniques in Computational Physics
Ice can take many geometric forms, from the uninteresting structure of ice cubes to the dendritic growth we examine in this paper. For an introduction to the morphology of possible ice crystal shapes, the reader is referred to the paper by Yokoyama and Kuroda29.
In addition to the visual appeal of dendritic crystals, their simulation is also of considerable practical interest. During the creation of alloys, a liquid to solid phase transition occurs, and if an dendrite forms in the melt during this process, the alloy can be drastically weakened. Consequently, there is a considerable body of work in the computational physics and crystal growth literature addressing this problem, and one of the most interesting simulation techniques that has emerged is the phase field method 16.
In its simplest form, the phase field method can be very computationally expensive. Therefore, various acceleration techniques have recently been developed to make the com¬putation more tractable. These include adaptive mesh refinement 20 and diffusion Monte Carlo 19 techniques. We will instead propose both a simpler scheme and a mapping to graphics hardware. Both techniques accelerate simulation performance and make it suitable for modeling modest scale ice growth.
At its core, the problem of dendritic solidification is one of tracking an evolving interface. Thus, the level set method 18, 22, an approach that has been widely used in computer graphics recently, can also be applied to the problem. While traditionally there have been problems in the use of level set methods to simulate dendritic solidification, many of them have been addressed in recent work 10. The level set method is also capable of providing a solution of higher order accu¬racy than the phase field method. However, we feel that this level of precision is unnecessary. Both the phase field and the level set methods can support an aesthetic parameterization, but we have chosen to use phase fields because it is simpler to implement and optimize, particularly on graphics hardware. Notably, the level set method is also an implicit simulation technique, and suffers from the same smoothing artifacts as the phase field method. Consequently, if level set methods were used in place of the phase field method, our geometric sharpening step would still be necessary.
Implementation
All the pipeline stages were implemented in less than 5000 lines of C++ code, excluding the third party libraries cited below. Excluding the runtime library infrastructure, the hardware implementation took less than 100 lines of Cg code.
For our Constrained Delaunay Triangulations, we used Jonathan Shewchuk’s Triangle package 23, a freely available Delaunay triangulation library that proved to be very well documented, easy to use, and highly optimized.
For rendering, we used POV-Ray 3.5, a freely available rendering application that supports a large shading language in addition to a nice photon map implementation.
Simulation Parameters
As mentioned earlier, the phase field simulation was run with the settings given in Table 1. The simulation ran successfully at the resolutions up to and including 2048 x 2048.
The time step was fixed to 0.0002 at all times. At larger steps, the numerical noise in the simulation quickly com¬pounded. Other higher-order methods, such as Midpoint and Runga-Kutta Four integration, were attempted as well. How¬ever, they were unable to reliably increase the timestep size by a factor that would have justified their cost.
Results
We successfully simulated ice growth in several scenes. All simulations took place on a 512 x 512 grid with the exceptions of Fig. 14, which was 512 x 800. Our graphics hard¬ware implementation runs at practically interactive rates, though its performance varies with the grid resolution. The first scene is a stained glass window, with ice growing in¬wards from the lead frame. Since the lead would cool faster than the glass, this seemed like a logical place to seed the ice. We ran the simulation for 600 iterations, taking a total of 34 seconds on a GeForceFX 5800 Ultra. The constant K was set to 1.2, and d was set to 0.04. We also inserted a small amount of random noise into the freezing temperature map to promote non-uniform growth. Fig. 1 shows a detailed view on a portion of the stained glass with ice grown on it. See Fig. 15 and 16 for a sequence of snapshots from the simulation.
The second scene is a pond with ice growing on a lily pad, as shown in Fig. 13 (a). We ran this simulation for 800 iter¬ations, taking a total of 45 seconds on the same GPU. The constant K was set to 1.2 and d was set to 0.1. The ring example, shown in Fig. 13(b), was run on the same processor, for 2300 iterations, taking a total of 130 seconds. The constant
K was set to 1.2 and d was set to 0.1. A larger stained glass window with a more complex pattern is shown in Fig. 14. We ran this simulation for 500 iterations, taking a total of 50 seconds on the same processor. The constant K was set to 1.2 and d was set to 0.1.
Summary and Future Work
We have presented a simulation technique from computational physics for the growth ice crystals and introduced optimizations to make the technique practical and interactive for computer graphics. We have also introduced a novel geometric sharpening operation to deal with the smoothing artifacts of the implicit simulation technique. Because ice growth has not been studied much in computer graphics in the past, there are many interesting future research directions.
The user parameterization we have presented is capable of preserving a desired shape, but the phase field model can support additional parameters for greater user control. The latent heat constant K, and the strength of anisotropy d, both influence the growth speed and the final shape of the ice, and their spatial mapping could be used to achieve different effects. Mapping the q0 parameter could also be used to suggest shapes, such as ice growth in a spiral. The effect of external forces, such as gravity, wind, and fluid flow, are currently under investigation, and have the potential to produce more interesting results.
With respect to rendering, we assumed homogeneous ice when in fact ice can exhibit subsurface scattering, spatially variant densities, and contain pockets of air in the form of bubbles or cracks. These issues need to be addressed for the accurate rendering of ice.
The phase field method simulates several, but not all,forms of ice crystal growth. These other types of ice crystal growth remain to be explored. Finally, the phase field method can be applied to fully 3D ice growth, capturing such phenomena as icicles. We plan to investigate other optimization techniques, such as parallel computation on a cluster of PCs, for efficient 3D simulation.
|